The present invention relates to permutation logic for changing words with uncorrectable errors (UE's) into memory words that can be corrected by the error correcting code protecting the data in the memory.
In copending Bossen et al. patent application Ser. No. 362,925 filed Mar. 29, 1982 and entitled "Deterministic Permutation Algorithm", a memory address register accesses a memory word by supplying the same logical address to decoders for all bit positions of the word. However, as a result of modification of logic circuitry the address actually applied to the decoder of any particular bit position can differ from the logical address supplied by the address register. The logic circuitry is called permutation logic. Because of the permutation logic, a memory word can contain storage cells located at a number of different physical addresses that are not the logical address supplied by the memory register.
The prior art permutation logic performs a single Exclusive OR function on each of the n inputs to the decoder of the particular bit position. Each of the n digits of the word address is Exclusive ORed with a different bit to permute the address.
If the bit decoder is a two bit decoder, the prior art permutation logic can provide to the decoder 2.sup.n or four different combinations or sequences of bit inputs. These are shown in Table 1.
TABLE I ______________________________________ Input Permutation Bits Bits Z1 Z0 C1,C0 00 01 10 11 ______________________________________ 00 00 01 10 11 01 01 00 11 10 10 10 11 00 01 11 11 10 01 00 ______________________________________
These four sequences form only a small subset of the possible decoder input sequences. There are actually 2.sup.n ! or 24 possible input sequences for a two bit decoder. The decimal equivalents of all possible sequences are shown in Table 2.
TABLE 2 __________________________________________________________________________ Decoder Inputs Possible Input Sequences Bits C1' C0' C1 C0 * * * * __________________________________________________________________________ 0 0 0 0 0 0 0 0 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 0 1 1 3 2 2 3 1 0 3 2 2 3 0 1 3 0 0 3 1 1 0 2 2 0 1 1 0 2 1 3 1 2 3 2 0 3 0 2 3 0 1 3 1 0 3 2 1 0 1 2 0 1 1 3 2 1 3 1 2 3 2 0 3 0 2 3 0 1 3 1 0 0 2 1 0 1 2 * * * * __________________________________________________________________________
It turns out that certain UE conditions cannot be satisfactorily resolved using any of the 2.sup.n input sequences in Table 1 where these same UE conditions could readily be allieviated in one of the other theoretically possible n! input sequences shown in Table 2 were achievable.
In addition to scattering faulty cells to change UE errors into correctable errors the mentioned prior art permutation logic has the ability of accumulating faulty memory elements in one of the memory words. This is done by using the bit address of the faulty elements as the permutation bits in the permutation logic. This is explained in an article entitled "Address Reconfiguration for Large Scale Integrated Memory Yield Enhancement" on page 1245 of the September 1973 issue of the IBM Technical Disclosure Bulletin. The problem with prior art bit permutation logic is that the capability of the prior art permutation logic is such that it cannot be used effectively to simultaneously both disperse and accumulate faulty bits.